import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
class WordDictionary {
    public String[] str;
    public WordDictionary() {
        this.str=new String[];
    }

    public void addWord(String word) {

    }

    public boolean search(String word) {

    }
}
public class project {

    public static void main(String[] args) {
        int[] arr={9,8,7,6,5,4,3,2,1};
        int gap=arr.length;
        while(gap>1){
            mySort(arr,gap);
            gap=(gap/3)+1;
        }
        mySort(arr,gap);
    }




    public static void mySort(int[] arr,int gap){
        for(int i=gap;i<arr.length;i+=gap){
            int tmp=arr[i];
            int j=i-gap;
            for(;j>=0;j-=gap){
                if(arr[i]>arr[j]){
                    arr[j+gap]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+gap]=tmp;
        }
    }









    public void mySort2(int[] arr){
        for(int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int left=0;
            int right=i;
            while(left<right){
                int mid=(left+right)/2;
                if(arr[mid]<=tmp){
                    left=mid+1;
                }else{
                    right=mid;
                }
            }
            for(int j=i;j>left;j--){
                arr[j]=arr[j-1];
            }
            arr[left]=tmp;
        }
    }







    public void mySort1(int[] arr){
        for(int i=1;i<arr.length;i++){
            int tmp=arr[i];
            int j=i-1;
            for(;j>=0;j--){
                if(arr[j]>tmp){
                    arr[j+1]=arr[j];
                }else{
                    break;
                }
            }
            arr[j+1]=tmp;
        }
    }







    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue=new PriorityQueue<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for(int i=0;i<Math.min(k,nums1.length);i++){
            for(int j=0;j<Math.min(k,nums2.length);j++){
                if(queue.size()<k){
                    List<Integer> list=new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    queue.offer(list);
                }else{
                    int tmp=queue.peek().get(0)+queue.peek().get(1);
                    if(tmp>nums1[i]+nums2[j]){
                        queue.poll();
                        List<Integer> list=new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        queue.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<k&&!queue.isEmpty();i++){
            list.add(queue.poll());
        }
        return list;
    }












    public List<List<Integer>> kSmallestPairs1(int[] nums1, int[] nums2, int k) {
        PriorityQueue<List<Integer>> queue=new PriorityQueue<>(new Comparator<List<Integer>>() {
            @Override
            public int compare(List<Integer> o1, List<Integer> o2) {
                return (o2.get(0)+o2.get(1))-(o1.get(0)+o1.get(1));
            }
        });
        for(int i=0;i<Math.min(nums1.length,k);i++){
            for(int j=0;j<Math.min(nums2.length,k);j++){
                if(queue.size()<k){
                    List<Integer> list=new ArrayList<>();
                    list.add(nums1[i]);
                    list.add(nums2[j]);
                    queue.offer(list);
                }else{
                    int tmp=queue.peek().get(0)+queue.peek().get(1);
                    if(tmp>nums1[i]+nums2[j]){
                        queue.poll();
                        List<Integer> list=new ArrayList<>();
                        list.add(nums1[i]);
                        list.add(nums2[j]);
                        queue.offer(list);
                    }
                }
            }
        }
        List<List<Integer>> list=new ArrayList<>();
        for(int i=0;i<k&&!queue.isEmpty();i++){
            list.add(queue.poll());
        }
        return list;
    }








    public List<Integer> findClosestElements(int[] arr, int k, int x) {
        int left=0;
        int right=arr.length-k;
        while(left<right){
            int mid=(left+right)/2;
            if(x-arr[mid]>arr[mid+k]-x){
                left=mid+1;
            }else{
                right=mid;
            }
        }
        List<Integer> list=new ArrayList<>();
        for(int i=left;i<left+k;i++){
            list.add(arr[i]);
        }
        return list;
    }







    public List<Integer> findClosestElements1(int[] arr, int k, int x) {
        int left=0;
        int right=arr.length-1;
        int remove=arr.length-k;
        while(remove>0){
            if(x-arr[left]<=arr[right]-x){
                right--;
            }else{
                left++;
            }
            remove--;
        }
        List<Integer> list=new ArrayList<>();
        for(int i=left;i<left+k;i++){
            list.add(arr[i]);
        }
        return list;
    }






    public int compareVersion(String version1, String version2) {
        String[] str1=version1.split("\\.");
        String[] str2=version2.split("\\.");
        int len1=str1.length;
        int len2=str2.length;
        int i=0;
        int j=0;
        while(i<len1||j<len2){
            int sum1=0;
            int sum2=0;
            if(i<len1){
                sum1=Integer.parseInt(str1[i++]);
            }
            if(j<len2){
                sum2=Integer.parseInt(str2[j++]);
            }
            if(sum1!=sum2){
                return sum1>sum2?1:-1;
            }
        }
        return 0;
    }
}
